package com.mc.sort;

public class HeapSort2 {
	private int[] heap;
	private int n;
	public HeapSort2(int[] heap){
		this.heap = heap;
		this.n = heap.length;
	}
	public void sort(){
		for(int i=1;i<n;i++){
			swim(i);
		}
		int k = n-1;
		while(k>=0){
			System.out.println(heap[0]);
			heap[0] = heap[k--];
			sink(0);
		}
	}
	private void sink(int i){
		while(2*i+1<n){//左孩子存在
			int j = 2*i+1;
			if(j+1<n&&heap[j]<heap[j+1])j++;
			if(heap[i]>=heap[j])break;
			int temp = heap[i];
			heap[i] = heap[j];
			heap[j] = temp;
			i=j;
		}
	}
	private void swim(int i){
		while(i>0&&heap[i]>heap[(i-1)/2]){
			int temp = heap[(i-1)/2];
			heap[(i-1)/2]=heap[i];
			heap[i]=temp;
			i=(i-1)/2;
		}
	}
	public static void main(String[] args){
		HeapSort2 hs = new HeapSort2(new int[]{1,6,9,3,4,8,9});
		hs.sort();
	}
}
